package dataStructs.tree;

import lombok.Data;

/**
 * @author Jonny Long
 * @date 2021/3/9 16:42
 */
@Data
public class BinarySortTree {
    private BSTNode root;

    // 先序遍历
    public void preOrder(BSTNode current) {
        if (current != null) {
            System.out.println(current);
            preOrder(current.getLeft());
            preOrder(current.getRight());
        }
    }

    // 中序遍历
    public void infixOrder(BSTNode current) {
        if (current != null) {
            infixOrder(current.getLeft());
            System.out.println(current);
            infixOrder(current.getRight());
        }
    }

    // 后序遍历
    public void postOrder(BSTNode current) {
        if (current != null) {
            postOrder(current.getLeft());
            postOrder(current.getRight());
            System.out.println(current);
        }
    }

    // 根据value查询节点(非递归方法)
    public BSTNode search(double value) {
        BSTNode p = this.root;
        while (p != null) {
            if (value < p.getValue()) {
                p = p.getLeft();
            } else if (value > p.getValue()) {
                p = p.getRight();
            } else {
                return p;
            }
        }
        return null;
    }

    // 根据value查询节点(递归方法)
    public BSTNode searchByRecursion(BSTNode current, double value) {
        if (current == null) {
            return null;
        }
        if (value < current.getValue()) {
            return searchByRecursion(current.getLeft(), value);
        } else if (value > current.getValue()) {
            return searchByRecursion(current.getRight(), value);
        } else {
            return current;
        }
    }

    // 查找最大值
    public BSTNode findMax() {
        BSTNode p = this.root;
        while (p.getRight() != null) {
            p = p.getRight();
        }
        return p;
    }

    // 查找最小值
    public BSTNode findMin() {
        BSTNode p = this.root;
        while (p.getLeft() != null) {
            p = p.getLeft();
        }
        return p;
    }

    // 查找某个节点的父亲节点
    public BSTNode searchParent(BSTNode node) {
        BSTNode p = this.root;
        while (p != null) {
            // 为了避免空指针异常，需要提前判断左孩子和右孩子是否为空
            if (p.getLeft() != null && p.getLeft().getValue() == node.getValue()) {
                return p;
            }
            if (p.getRight() != null && p.getRight().getValue() == node.getValue()) {
                return p;
            }
            if (node.getValue() > p.getValue()) {
                p = p.getRight();
            } else {
                p = p.getLeft();
            }
        }
        return null;
    }

    // 插入节点(非递归方法)
    public void insert(BSTNode node) {
        BSTNode p = this.root;
        if (node == null) {
            return;
        }
        while (p != null) {
            if (node.getValue() < p.getValue()) {
                if (p.getLeft() == null) {
                    p.setLeft(node);
                    break;
                } else {
                    p = p.getLeft();
                }
            } else {
                if (p.getRight() == null) {
                    p.setRight(node);
                    break;
                } else {
                    p = p.getRight();
                }
            }
        }
    }

    /**
     * 删除二叉排序树中的某个节点，并将其子节点连接上去
     */
    public void delete(BSTNode node) {

    }

    // 销毁二叉排序树
    private void destroy(BSTNode tree) {
        if (tree == null)
            return;
        if (tree.getLeft() != null) {
            destroy(tree.getLeft());
        }
        if (tree.getRight() != null) {
            destroy(tree.getRight());
        }
        tree = null;
    }


}
